﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：1221. 四平方和
//四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 4个正整数的平方和。
//如果把 0包括进去，就正好可以表示为 4个数的平方和。
//比如：
//5 = 02 + 02 + 12 + 22
//7 = 12 + 12 + 12 + 22
//对于一个给定的正整数，可能存在多种平方和的表示法。
//要求你对 4个数排序：
//0≤a≤b≤c≤d
//并对所有的可能表示法按 a, b, c, d为联合主键升序排列，最后输出第一个表示法。
//输入格式
//输入一个正整数 N。
//输出格式
//输出4个非负整数，按从小到大排序，中间用空格分开。
//数据范围
//0 < N < 5∗106
//输入样例：
//5
//输出样例：
//0 0 1 2
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N = 5 * 1e6;
//struct Sum {
//    int s, c, d;
//    bool operator< (const Sum& t) const {//重载小于号
//        if (s != t.s) return s < t.s;//先按总和从小到大排序
//        else if (c != t.c) return c < t.c;//若总和相同，则按照c从小到大排序
//        else return d < t.d;//若总和c均相同，则按照d从小到大排序
//    }
//}S[N];
//
//int n, m;
//
//int main() {
//    //如果暴力枚举会超时，思考空间换时间，
//    //先枚举cd所有情况，把cd的情况当成sum这个整体，从小到大枚举ab，二分查sum（cd）
//    cin >> n;
//    for (int c = 0; c * c <= n; ++c) {      //先枚举cd的所有情况
//        for (int d = c; c * c + d * d <= n; ++d) //c<d
//            S[m++] = { c * c + d * d, c, d };//添加时满足c<=d，计算枚举c * c + d * d <= n的所有情况
//    }
//
//    sort(S, S + m);//排序，最终效果是 总和s 从小到大
//    //a*a+b*b+（c*c+d*d）=n   由于（c*c+d*d）的情况均枚举完了，可以把这个当作一个整体Sum，二分找a*a+b*b=n-Sum
//    for (int a = 0; a * a <= n; ++a) {
//        for (int b = a; a * a + b * b <= n; ++b) {//枚举a<=b,从a=b=0开始找sum
//            int t = n - a * a - b * b;
//            //二分查找满足a*a+b*b=n-Sum的Sum
//            int l = 0, r = m - 1;
//            while (l < r) {
//                int mid = l + r >> 1;
//                if (S[mid].s >= t) r = mid;
//                else l = mid + 1;
//            }
//            if (S[l].s == t) {
//                cout << a << " " << b << " " << S[l].c << " " << S[l].d << endl;
//                return 0;
//            }
//        }
//    }
//
//    return 0;
//}
